1. Field of the Invention
The present invention relates to memory management schemes for use in data communications, specifically packet routing.
2. Description of the Related Art
Within routers and switches today, the process whereby the routing function is carried out is well known in the art. Part of that process is the step of determining whether or not a router is aware of the corresponding next hop destination for packet routing. This typically uses a lookup of certain elements of the packet or cell header in a table to determine packet routing, such as a longest Internet Protocol (IP) prefix match for a destination address derived from the packet header. Many systems exist for determining such matches, both in the context of Internet Protocol routing as well as other forms of routing and switching (such as those employed with the asynchronous transfer mode [ATM] communications). See for example, U.S. Pat. No. 5,809,501 to Noven, entitled Method and System of Database Management and an Asynchronous Transfer Mode (ATM) Environment and U.S. Pat. No. 5,884,297 also to Noven, entitled System and Method for Maintaining a Table in Content Addressable Memory Using Hole Algorithms. Both of these patents are incorporated herein by reference in their entireties.
As is well-known in the art, a content addressable memory (CAM) lookup outputs an exact match: either the parameter to be looked up (i.e., the lookup key) is in the CAM table or it is not. If the key is found in the table, an exact match exists and the address in the CAM table where the entry was found is provided as the output of the lookup. Ternary CAMs (TCAMs) differ from CAMs in that a TCAM allows the user to mask off bits such that a lookup key is said to match a TCAM entry even if all bits in the key do not match the entry. In other words, by masking out certain bits in the TCAM as xe2x80x9cdon""t carexe2x80x9d bits, more than one lookup key can be said to match a TCAM entry. If several TCAM entries match the lookup key, the top-most one (i.e., the entry having the lowest address) is returned. This feature is useful in supporting the longest IP prefix lookup function because the object of the search is only to find the longest prefix match, not to find all exact matches of the entire key. Commonly, the mask function of the TCAM is used to remove (mask off) non-prefix bits in the TCAM so that the lookup speed is increased in a longest prefix match lookup.
Longest prefix lookups are commonly implemented using a TCAM by placing the prefix entries in the TCAM in descending order, sorted by the length of the prefix in each entry. FIG. 1 illustrates a prior art TCAM-implemented lookup table 100 containing sorted prefix entries 110. The non-prefix bits of the IP address in the TCAM are generally masked off at the time of lookup. For Internet Protocol version 4 (IPv4), the IP addresses are 32 bits long: sorting these addresses into a TCAM thus creates a table having 32 different regions (not shown), where each region 1 consists of entries of a prefix length i, i being the number of unique prefix bits in an entry. (Note that in the upcoming standard Internet Protocol version 6 (IPv6), the IP address is 128 bits. IPv6 will thus necessitate a TCAM having 128 distinct IP prefix length regions.)
FIG. 1 shows a representative prior art TCAM containing a number of entries 110. Entries 110 that are empty (i.e., not having a prefix stored therewithin) are labeled as xe2x80x9cholesxe2x80x9d 120. (Entries having a prefix stored therewithin are labeled xe2x80x9c130xe2x80x9d.) The highest address entry is 110-A, here containing a prefix 130. The lowest address entry (in the bottom-most position) in TCAM table 100 is 110-Z, here containing a hole 120.
Although a TCAM addressing scheme having the lowest address at the xe2x80x9cbottomxe2x80x9d of the memory array is described, those skilled in the art will realize that such an organization is merely conceptual and that other conceptualizations and/or physical content-addressable memory layouts can be used. Accordingly, the present invention is not limited to any particular address ordering. Both the xe2x80x9clowest address on topxe2x80x9d and xe2x80x9clowest address on bottomxe2x80x9d orderings can be used with appropriate adaptations of the methods and apparatus described herein. Such adaptation is well within the skill of one of ordinary skill in the art and requires no undue experimentation.
Furthermore, FIG. 1 is only a representative illustration of a portion of a TCAM configured for longest prefix match lookups. One of ordinary skill in the art will readily understand that TCAMs, and CAMs generally, having widths greater than 32 bits are commonly used and that the xe2x80x9cdepthxe2x80x9d (i.e., the number of available entries) of the TCAM can vary.
In operation, lookup key 105 is compared to every entry 110 in TCAM 100. The comparison of key 105 to all entries in TCAM 100 is done simultaneously by a bit-wise NOT(XOR) with every unmasked bit in every entry. If an AND function of the results of all of the NOT(XOR) operations for an entry 110 is TRUE, the all bits of that entry 110 match key 105. The address of the highest addressed (and therefore longest prefix) entry is provided to the TCAM output.
Although the ability of the TCAM to rapidly produce longest prefix lookup matches is advantageous, it complicates the task of inserting and deleting new prefixes within the TCAM table. This is so because the TCAM table must be maintained in a prefix length sorted order. Though TCAM updates (inserts and deletes) are infrequent, a time consuming update mechanism steals valuable processor resources and potentially results in a dropping of packets. Such deleterious effects must be avoided if high packet switching/routing speeds are to be maintained. The problem is only exacerbated by the expected industry switch to the IPv6 architecture with its longer addresses.
An insert of a prefix of length i can be accomplished in one TCAM write cycle if there is a vacant entry (hole) in the ith region (i.e., the region containing all entries of equal length i), otherwise the TCAM write may need to move a vacant entry from a neighboring region in order to expand the space in the ith region. In particular, if up to k regions on either side of the ith region have no holes, then one would need to perform k moves to provide a hole. Since the cost of a move (involving both reading and writing the entry) is much higher than that of a lookup, it is desirable to minimize the number of moves involved in TCAM updates.
In one prior art method commonly used, a xe2x80x9cnaxc3xafvexe2x80x9d algorithm for TCAM updates is employed. The naxc3xafve (or xe2x80x9clazyxe2x80x9d) algorithm moves TCAM entries only when it needs to. A delete in a given region creates a hole in that region. Conversely, an insert in a region requires the presence of a hole in that region in which to insert the entry. A region is referred to as a xe2x80x9cfullxe2x80x9d (or xe2x80x9ccongestedxe2x80x9d) region when it does not have any holes and thus an insert into a full region requires moving a hole into that region from the nearest non-full region. This may necessitate moving entries in adjoining regions as well, in order to make room. It is desirable that the number of moves required to supply a hole to a full region is minimized. Indeed, it is preferable to have some holes in each region to facilitate updating.
Consider a TCAM with a certain maximum number of entries. One can readily see that some routing applications could use enough IP prefixes to result in a TCAM occupancy rate of 90% or more. In fact, such occupancy rates are commonly seen in the art today. A 90% occupancy rate implies that 10% of the TCAM entries are holes. A xe2x80x9cgood distributionxe2x80x9d of these holes is one where they are almost equally distributed among the 32 regions (in an IPv4 system, which has a maximum prefix length of 32 bits) so that one does not encounter a full region during any insert. Obviously, a xe2x80x9cbad distributionxe2x80x9d is one where several full regions occur contiguously, resulting in the requirement for a number of moves in order to provide a hole to support an insertion.
A good TCAM update algorithm will thus try to ensure that if one starts with a good distribution of holes among the regions, then after several updates the hole distribution will remain good. The naxc3xafve algorithm unfortunately gets stuck in a bad distribution once it reaches that state and never recovers on its own. If k full regions occur contiguously at any point, then the naxc3xafve algorithm incurs an average cost of k/2 moves for every future insert into one of those regions. For example, if the lowest-addressed (bottom-most) one third of the prefix regions in the TCAM increase in size by 10%, they will borrow holes from the middle third. This can result in a complete lack of holes in the middle region, which is too large for a naxc3xafve algorithm to compensate. This cost results in a packet processing delay, which can in turn cause packet drops.
A study of the problem has indicated that a good TCAM update algorithm has the following desirable properties: (a) Given a good distribution of holes among regions, the distribution should tend to remain good after several updates; and (b) Even if the TCAM is forced into a bad distribution, the update algorithm should automatically recover to a good distribution with future updates.
Another basic problem with the prior art naxc3xafve algorithm is that, even if there are holes within a region available for insert, one still needs to search for them, again incurring undesirable delays. Because these holes may be scattered throughout the region, finding one can become an expensive task in terms of processor resources. There are presently two approaches commonly used in such situations. On the one hand, one could go through the entire region looking for available holes. This method is time consuming and thus could lead to packet drops. Alternately, one could maintain a doubly-linked list of holes for each region in storage device external to the TCAM and use that data structure to locate a hole. Though this approach allows one to locate a hole in a constant amount of time (independent of the size of the region, number of holes, and the number of regions, a period represented in algorithmic analysis literature as order-1 or xe2x80x9cO(1)xe2x80x9d time complexity), it requires maintaining complicated data structures in the TCAM controller. Any hardware or firmware implementation of the TCAM controller would thus consume additional (and scarce) memory and code space resources.
What is needed is an efficient algorithm for TCAM updates and an associated TCAM organization scheme that enables rapid location and utilization of holes in a given region of the memory.
Presently described are techniques for the efficient location of free entries or xe2x80x9cholesxe2x80x9d for use in performing insert operations in a binary or ternary content addressable memory. TCAMs, as used in data communications and packet routing, often rely on an organization that maintains entries of the same xe2x80x9clengthxe2x80x9d within defined regions. The present invention keeps the holes (that is, the memory locations within the TCAM that have no data written into them) compacted into a contiguous subregion within each region. Advantageously, this compaction does not require movement of the holes during a delete operation. The present invention has the further advantage of keeping all of the holes sorted by TCAM region. These positive effects are accomplished by initially pre-filling the entire memory with a set of hole codes that uniquely identify the holes in each region.
After the memory is initialized, a conventional memory write is performed to put the initial state of the routing data into the memory. Typically, such routing data will not fill the entire memory, leaving unused entries (containing the region-unique hole code) in each region.
In operation, as entries need to be added or deleted, the present invention provides a rapid and efficient mechanism whereby entries to be deleted can be simply replaced by the region-unique hole code. Likewise, to insert data in an entry, the host processor simply needs to search for a hole code in the region of interest. In instances where a region has no available holes, a simple mechanism is presented to allow movement of a hole from a nearby region. Anytime a hole is created within the xe2x80x9cusedxe2x80x9d subregion of a region, that hole (being the top-most hole in the region) will be the first to be filled on a subsequent insertion. Accordingly, the used entries and the holes will each be kept in contiguous subregions within each region, providing an efficient usage of memory resources.